<article aria-label="Readme">
    <div class="_wrapper_g1cur3">

<h1><a href="#ego-tree" id="user-content-ego-tree" rel="nofollow noopener noreferrer"></a>Ego Tree</h1>
<p><a href="https://crates.io/crates/ego-tree" rel="nofollow noopener noreferrer"><img src="https://img.shields.io/crates/v/ego-tree?color=dark-green" alt="crates.io"></a>
<a href="https://crates.io/crates/ego-tree" rel="nofollow noopener noreferrer"><img src="https://img.shields.io/crates/d/ego-tree" alt="downloads"></a>
<a href="https://github.com/rust-scraper/ego-tree/actions/workflows/test.yml" rel="nofollow noopener noreferrer"><img src="https://github.com/rust-scraper/ego-tree/actions/workflows/test.yml/badge.svg" alt="test"></a></p>
<p><code>ego-tree</code> is a Rust crate that provides a Vec-backed ID-tree implementation. It offers a flexible and efficient way to create and manipulate tree structures in Rust, with a focus on performance and ease of use.</p>
<p><code>ego-tree</code> is on <a href="https://crates.io/crates/ego-tree" rel="nofollow noopener noreferrer">Crates.io</a> and <a href="https://github.com/rust-scraper/ego-tree" rel="nofollow noopener noreferrer">GitHub</a>.</p>
<h2><a href="#design-philosophy" id="user-content-design-philosophy" rel="nofollow noopener noreferrer"></a>Design Philosophy</h2>
<p>The design of <code>ego-tree</code> is centered around the following principles:</p>
<ol>
<li>
<p><strong>Efficiency</strong>: The tree structure is backed by a Vec, allowing for fast, cache-friendly operations and efficient memory usage.</p>
</li>
<li>
<p><strong>Flexibility</strong>: Nodes can have any number of children, allowing for the representation of various tree structures.</p>
</li>
<li>
<p><strong>Stability</strong>: Node references remain valid even after modifying the tree structure, thanks to the use of stable NodeId indices.</p>
</li>
<li>
<p><strong>Safety</strong>: The API is designed to prevent common errors, such as creating cycles or detaching the root node.</p>
</li>
<li>
<p><strong>Ergonomics</strong>: The crate provides both low-level operations and high-level conveniences like the <code>tree!</code> macro for easy tree construction.</p>
</li>
</ol>
<h2><a href="#key-design-choices" id="user-content-key-design-choices" rel="nofollow noopener noreferrer"></a>Key Design Choices</h2>
<h3><a href="#vec-backed-structure" id="user-content-vec-backed-structure" rel="nofollow noopener noreferrer"></a>Vec-Backed Structure</h3>
<p>Unlike traditional pointer-based trees, <code>ego-tree</code> uses a Vec to store all nodes. This design choice offers several advantages:</p>
<ul>
<li>Improved cache locality, potentially leading to better performance</li>
<li>Simplified memory management</li>
<li>Easier serialization and deserialization</li>
<li>Constant-time access to any node by its ID</li>
</ul>
<h3><a href="#node-ids" id="user-content-node-ids" rel="nofollow noopener noreferrer"></a>Node IDs</h3>
<p>Nodes are identified by <code>NodeId</code>s, which are wrappers around indices into the underlying Vec. This approach allows for:</p>
<ul>
<li>Stable references to nodes, even as the tree structure changes</li>
<li>Efficient node lookup (O(1) time complexity)</li>
<li>Compact representation of relationships between nodes</li>
</ul>
<h3><a href="#immutable-and-mutable-node-references" id="user-content-immutable-and-mutable-node-references" rel="nofollow noopener noreferrer"></a>Immutable and Mutable Node References</h3>
<p>The crate provides both <code>NodeRef</code> (immutable) and <code>NodeMut</code> (mutable) types for working with nodes. This separation allows for:</p>
<ul>
<li>Clear distinction between read-only and modifying operations</li>
<li>Prevention of multiple mutable references to the same node, enforcing Rust's borrowing rules</li>
<li>Efficient implementation of various tree traversal iterators</li>
</ul>
<h3><a href="#orphan-nodes" id="user-content-orphan-nodes" rel="nofollow noopener noreferrer"></a>Orphan Nodes</h3>
<p>Nodes can be detached from the tree but not removed entirely. This design choice:</p>
<ul>
<li>Simplifies certain tree manipulation algorithms</li>
<li>Allows for temporary detachment and reattachment of subtrees</li>
<li>Maintains the validity of NodeIds, even for detached nodes</li>
</ul>
<h3><a href="#rich-iterator-support" id="user-content-rich-iterator-support" rel="nofollow noopener noreferrer"></a>Rich Iterator Support</h3>
<p>The crate provides a variety of iterator types for traversing the tree in different ways. This design:</p>
<ul>
<li>Allows for efficient and idiomatic tree traversal</li>
<li>Supports various algorithms and use cases without sacrificing performance</li>
<li>Leverages Rust's powerful iterator ecosystem</li>
</ul>
<h2><a href="#use-cases" id="user-content-use-cases" rel="nofollow noopener noreferrer"></a>Use Cases</h2>
<p><code>ego-tree</code> is well-suited for applications that require:</p>
<ul>
<li>Efficient representation and manipulation of hierarchical data structures</li>
<li>Frequent traversal and modification of tree structures</li>
<li>Stable references to tree nodes across operations</li>
<li>Serialization and deserialization of tree structures</li>
</ul>
<p>Some potential use cases include:</p>
<ul>
<li>DOM-like structures for document processing</li>
<li>File system representations</li>
<li>Organizational hierarchies</li>
<li>Game scene graphs</li>
<li>Abstract syntax trees for compilers or interpreters</li>
</ul>
<h2><a href="#getting-started" id="user-content-getting-started" rel="nofollow noopener noreferrer"></a>Getting Started</h2>
<p>Add this to your <code>Cargo.toml</code>:</p>
<pre><code class="language-toml hljs language-ini" data-highlighted="yes"><span class="hljs-section">[dependencies]</span>
<span class="hljs-attr">ego-tree</span> = <span class="hljs-string">"0.6.2"</span>
</code></pre>
<p>Basic usage:</p>
<pre><code class="language-rust hljs" data-highlighted="yes"><span class="hljs-keyword">use</span> ego_tree::Tree;

<span class="hljs-keyword">let</span> <span class="hljs-keyword">mut </span><span class="hljs-variable">tree</span> = Tree::<span class="hljs-title function_ invoke__">new</span>(<span class="hljs-number">1</span>);
<span class="hljs-keyword">let</span> <span class="hljs-keyword">mut </span><span class="hljs-variable">root</span> = tree.<span class="hljs-title function_ invoke__">root_mut</span>();
root.<span class="hljs-title function_ invoke__">append</span>(<span class="hljs-number">2</span>);
<span class="hljs-keyword">let</span> <span class="hljs-keyword">mut </span><span class="hljs-variable">child</span> = root.<span class="hljs-title function_ invoke__">append</span>(<span class="hljs-number">3</span>);
child.<span class="hljs-title function_ invoke__">append</span>(<span class="hljs-number">4</span>);
child.<span class="hljs-title function_ invoke__">append</span>(<span class="hljs-number">5</span>);
</code></pre>
<p>For more detailed usage examples and API documentation, please refer to the <a href="https://docs.rs/ego-tree" rel="nofollow noopener noreferrer">documentation</a>.</p>
<h2><a href="#license" id="user-content-license" rel="nofollow noopener noreferrer"></a>License</h2>
<p>This project is licensed under the ISC License.</p>
<h2><a href="#contributing" id="user-content-contributing" rel="nofollow noopener noreferrer"></a>Contributing</h2>
<p>Contributions are welcome! Please feel free to submit a Pull Request.</p>
<h2><a href="#credits" id="user-content-credits" rel="nofollow noopener noreferrer"></a>Credits</h2>
<p><code>ego-tree</code> is created and maintained by the team of <a href="https://github.com/rust-scraper" rel="nofollow noopener noreferrer">rust-scraper</a>.</p>


</div>
  </article>